﻿#include<iostream>
#include<vector>
#include<unordered_map>
#include<list>
#include<algorithm>
using namespace std;




//合并区间
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.size() == 0)
    {
        return {};
    }
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged;
    for (int i = 0; i < intervals.size(); ++i)
    {
        int L = intervals[i][0], R = intervals[i][1];
        if (!merged.size() || merged.back()[1] < L)
        {
            merged.push_back({ L, R });
        }
        else //可以合并
        {
            merged.back()[1] = max(merged.back()[1], R);//更新右端点最大值
        }
    }

    return merged;

}

//连续数组
int findMaxLength(vector<int>& nums) {
    unordered_map<int, int> hash;
    hash[0] = -1; // 默认有⼀个前缀和为 0 的情况
    int sum = 0, ret = 0;
    for (int i = 0; i < nums.size(); i++)
    {

        sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和
        if (hash.count(sum))
        {
            ret = max(ret, i - hash[sum]);
        }
        else
        {
            hash[sum] = i;
        }
    }
    return ret;
}


int main()
{
    vector<vector<int>> num1 = { {1,3},{2,6},{8,10},{15,18} };
    vector<vector<int>> sum1 = merge(num1);
    for (auto i : sum1)
    {
        for (auto j : i)
        {
            cout << j << " ";

        }
        cout << endl;
    }

    vector<int> num2 = { 0,1 };
    int sum2 = findMaxLength(num2);
    cout << sum2;

    return 0;

}